 /*
Universidade de Brasilia
Instituto de Ciencias Exatas
Departamento de Ciencia da Computacao
Seguranca de Dados 01/2010
Aluno: Thiago Melo Stuckert do Amaral
Matricula: 06/96773
Turma: A

Descricao: Quebra da cifra de vigenere.
urls:
http://www.cic.unb.br/docentes/pedro/segdados_files/lista1.htm
http://en.wikipedia.org/wiki/Vigenère_cipher
*/
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#define MAX_ENCRYPTED 700
#define MAX_TAM_CHAVE 22
#define TAM_ASCII 256

/*Mensagem encriptada*/
int encrypted[MAX_ENCRYPTED];
int tam_encrypted;

/*Chave utilizada para decriptar*/
int chave[MAX_TAM_CHAVE];
int tam_chave;

/*
  Procura o tamanho da chave
  Para isto busca a distancia das palavras iguais no texto.
*/
void busca_tam(){
  int i,j,k,l,shift,t,maior;
  int chaves[MAX_ENCRYPTED];
  memset(chaves,0,sizeof(chaves));

  for(shift=0;shift<tam_encrypted;shift++){
    for(j=shift,i=0;i<tam_encrypted;j++,i++){
      if(j==tam_encrypted) j=0;
      if(encrypted[i]==encrypted[j]){
		  i++;
		  j++;if(j==tam_encrypted)j=0;
		  l=i;
		  k=j;
		  t=1;
		  while(l<tam_encrypted && encrypted[l]==encrypted[k]){
			  t++;
			  k++;
			  if(k==tam_encrypted)k=0;
			  l++;
		  }
		  chaves[shift]++;	
      }
    }
  }

  maior=-1;
  for(k=2;k<MAX_TAM_CHAVE;k++)
    if(chaves[k]>maior){
      maior=chaves[k];
      tam_chave=k;
    }
}

/*vetor aonde armazenado as frequencias das letras do texto original*/
int freq[TAM_ASCII];

void inicializa_freq(){
	memset(freq,0,sizeof(freq));
	freq[32]=93;
	freq[101]=64;
	freq[97]=58;
	freq[111]=52;
	freq[115]=49;
	freq[100]=40;
	freq[114]=35;
	freq[109]=32;
	freq[105]=27;
	freq[110]=25;
	freq[117]=24;
	freq[116]=18;
	freq[112]=15;
	freq[99]=12;
	freq[108]=12;
	freq[118]=8;
	freq[102]=7;
	freq[44]=5;
	freq[231]=4;
	freq[46]=3;
	freq[98]=3;
	freq[103]=3;
	freq[113]=3;
	freq[227]=3;
	freq[120]=2;
	freq[122]=2;
	freq[59]=1;
	freq[65]=1;
	freq[69]=1;
	freq[201]=1;
	freq[225]=1;
	freq[233]=1;
	freq[234]=1;
	freq[243]=1;
	freq[244]=1;
	freq[245]=1;
}

/*Frequencia apenas nas letras da i-esima coluna*/
int freq_aux[TAM_ASCII];

/*Percorre o texto contando quantas vezes cada letra ocorre na i-esima coluna*/
void inicializa_freq_aux(int pos){
  int i;
  memset(freq_aux,0,sizeof(freq_aux));
  for(i=pos;i<tam_encrypted;i+=tam_chave){
    freq_aux[encrypted[i]]++;
  }
}

void procura_chave(){
  int i,j,k,l,h;
  int caracter_maior_frequencia_texto_encriptado;
  int caracter_maior_frequencia_texto_original;
	
  /*Heuristica utilizada bater a maior frequencia da coluna com a maior frequencia do texto*/
  h=-1;
  for(i=0;i<TAM_ASCII;i++)
    if(freq[i]>h){
      h=freq[i];
      caracter_maior_frequencia_texto_original=i;
    }
  
  for(i=0;i<tam_chave;i++){
    inicializa_freq_aux(i);
    
    h=-1;
    for(j=0;j<TAM_ASCII;j++){
      if(freq_aux[j]>h){
		  h=freq_aux[j];
		  caracter_maior_frequencia_texto_encriptado=j;
      }
    }
    chave[i]=caracter_maior_frequencia_texto_encriptado^caracter_maior_frequencia_texto_original;
  }
	
  /*Modifiquei essas posicoes da chave apos reconhecer as palavras no texto decriptado*/
  chave[1]=10;
  chave[3]=107;
	
  printf("Chave encontrada: ");
  for(i=0;i<tam_chave;i++)
	  printf("%d ",chave[i]);

  printf("\n");
}

void decripta(){
  int i,j;
  printf("Texto decifrado: ");
  for(i=0,j=0;i<tam_encrypted;i++,j++){
    if(j==tam_chave) j=0;
    printf("%c",(unsigned char)(encrypted[i] ^ chave[j]));
  }
  printf("\n");
}

int main () {
  int d;
  tam_encrypted=0;
  while(scanf("%d\n",&d)!=EOF){
    encrypted[tam_encrypted++]=d;
  }
  busca_tam();
  inicializa_freq();
  procura_chave();
  decripta();
  return 0;
}
